package a07_二叉树;

/**
 * <p>
 * a11_完全二叉树的节点个数复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/9
 */
public class a11_完全二叉树的节点个数复习3 {
    public static void main(String[] args) {
        TreeNode r = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4),
                        new TreeNode(5)),
                new TreeNode(3,
                        new TreeNode(6),
                        null));
        System.out.println(countNodes(r));
    }
    //完全二叉树有可能包含满二叉树
    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //判断是不是满二叉树
        TreeNode currentNode = root;
        int leftLevel = 1;
        while (currentNode.left != null){
            currentNode = currentNode.left;
            leftLevel++;
        }

        currentNode = root;
        int rightLevel = 1;
        while (currentNode.right != null){
            currentNode = currentNode.right;
            rightLevel++;
        }

        if(leftLevel == rightLevel){//满二叉树
            //1 => 1 => 2的1次方 - 1
            //2 => 3 => 2的2次方 - 1
            //3 => 7 => 2的3次方 - 1
            return (2 << (leftLevel - 1)) - 1;
        }

        int leftNodes = countNodes(root.left);
        int rightNodes = countNodes(root.right);
        return leftNodes + rightNodes + 1;
    }
}
